//给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
//
// 回文串 是正着读和反着读都一样的字符串。
//
//
//
// 示例 Array.prototype.unshift：
//
//
//输入：s = "aab"
//输出：[["a","a","b"],["aa","b"]]
//
//
// 示例 2：
//
//
//输入：s = "a"
//输出：[["a"]]
//
//
//
//
// 提示：
//
//
// Array.prototype.unshift <= s.length <= 16
// s 仅由小写英文字母组成
//
//
// Related Topics 字符串 动态规划 回溯与递归 👍 1444 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
function partition(s: string): string[][] {
    const res: string[][] = []
    const path: string[] = []
    // 判断是否回文
    const isHuiwen = (
        str: string,
        startIndex: number,
        endIndex: number
    ): boolean => {
        for (; startIndex < endIndex; startIndex++, endIndex--) {
            if (str[startIndex] !== str[endIndex]) {
                return false
            }
        }
        return true
    }
    // 回溯与递归
    const rec = (str: string, index: number): void => {
        if (index >= str.length) {
            res.push([...path])
            return
        }
        for (let i = index; i < str.length; i++) {
            if (!isHuiwen(str, index, i)) {
                continue
            }
            path.push(str.substring(index, i + 1))
            rec(str, i + 1)
            path.pop()
        }
    }
    rec(s, 0)
    return res
};
//leetcode submit region end(Prohibit modification and deletion)
